Stochastic Matrix
Table of Contents
- Probability Matrix, Transition Matrix, Substitution Matrix, Markov Matrix
1. Definition
- Right Stochastic Matrix
- Square matrix of nonnegative real numbers, with each row summing to 1.
- Left Stochastic Matrix
- Square matrix of nonnegative real numbers, with each column summing to 1.
- \(\mathrm{P}[j|i] = P_{ij}\)
2. Properties
- It is a square matrix that describes the transitions of a , with its entries representing a probability.
3. Doubly Stochastic Matrix
- Bistochastic
3.1. Definition
A square matrix of nonnegative real numbers, with each rows and columns summing to 1: \[ \sum_i x_{ij} = \sum_jx_{ij} = 1. \]
3.2. Properties
- Doubly stochastic matrix is both left stochastic and right stochastic.
4. Birkhoff Polytope
The class of \(n\) by \(n\) doubly stochastic matrices is a convex polytope called the Birkhoff polytope \(B_n\)
5. Birkhoff-von Neumann Theorem
- Birkhoff's Theorem
The polytope \(B_n\) is the convex hull of the set of \(n\) by \(n\) permutation matrices:
\begin{align*} &X\ \text{doubly stochastic matrix} \\ \implies &\exists \theta_1,\dots,\theta_k \ge 0, \sum_{i=1}^k\theta_i = 1, \\ &\exists P_1,\dots, P_k\ \text{permutation matrix}, X = \sum_{i=1}^k \theta_iP_i \end{align*}Furthermore, the vertices of \(B_n\) are precisely the permutation matrices.
The representation of a doubly stochastic matrix is known as the Birkhoff-von Neumann decomposition, and may not be unique.